#include <bits/stdc++.h>
using namespace std;

/*
778. 水位上升的泳池中游泳
已解答
困难
相关标签
premium lock icon
相关企业
提示
在一个 n x n 的整数矩阵 grid 中，每一个方格的值 grid[i][j] 表示位置 (i, j) 的平台高度。

当开始下雨时，在时间为 t 时，水池中的水位为 t 。你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没这两个平台。假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的。当然，在你游泳的时候你必须待在坐标方格里面。

你从坐标方格的左上平台 (0，0) 出发。返回 你到达坐标方格的右下平台 (n-1, n-1) 所需的最少时间 。

 

示例 1:



输入: grid = [[0,2],[1,3]]
输出: 3
解释:
时间为0时，你位于坐标方格的位置为 (0, 0)。
此时你不能游向任意方向，因为四个相邻方向平台的高度都大于当前时间为 0 时的水位。
等时间到达 3 时，你才可以游向平台 (1, 1). 因为此时的水位是 3，坐标方格中的平台没有比水位 3 更高的，所以你可以游向坐标方格中的任意位置
示例 2:



输入: grid = [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
输出: 16
解释: 最终的路线用加粗进行了标记。
我们必须等到时间为 16，此时才能保证平台 (0, 0) 和 (4, 4) 是连通的
 

提示:

n == grid.length
n == grid[i].length
1 <= n <= 50
0 <= grid[i][j] < n2
grid[i][j] 中每个值 均无重复
*/

// 法一
class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        int n = grid.size();
        if (n == 1) return grid[0][0];
        
        int low = grid[0][0]; // 起点高度是最低可能时间（必须淹没起点）
        int high = 0;
        for (auto& row : grid) {
            for (int val : row) {
                high = max(high, val);
            }
        }
        
        vector<pair<int, int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        vector<vector<bool>> visited(n, vector<bool>(n, false));
        
        while (low < high) {
            int mid = low + (high - low) / 2;
            // 重置访问标记
            for (auto& row : visited) fill(row.begin(), row.end(), false);
            
            // 关键修复：先检查起点是否可访问（高度 <= mid）
            if (grid[0][0] > mid) {
                low = mid + 1;
                continue;
            }
            
            if (canReach(grid, visited, dirs, 0, 0, mid, n)) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        
        return low;
    }
    // helper
    bool canReach(vector<vector<int>>& grid, vector<vector<bool>>& visited, 
                 vector<pair<int, int>>& dirs, int x, int y, int t, int n) {
        // 到达终点
        if (x == n - 1 && y == n - 1) {
            return true;
        }
        
        visited[x][y] = true;
        
        for (auto& [dx, dy] : dirs) {
            int nx = x + dx;
            int ny = y + dy;
            // 检查：1. 边界 2. 未访问 3. 高度 <= t（当前水位可淹没）
            if (nx >= 0 && nx < n && ny >= 0 && ny < n 
                && !visited[nx][ny] 
                && grid[nx][ny] <= t) {
                if (canReach(grid, visited, dirs, nx, ny, t, n)) {
                    return true;
                }
            }
        }
        
        return false;
    }
};

// 法二
static const int dirs[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 四向移动偏移量（上、右、下、左）

class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        int n = grid.size();
        // 访问标记：用当前检查的水位mx作为标记值，避免每次二分都重置数组（优化点）
        // vis[x][y] == mx 表示在当前mx的检查中已访问过该单元格
        vector<vector<int>> vis(n, vector<int>(n, -1));

        // 检查水位为mx时，是否存在从(0,0)到(n-1,n-1)的路径
        auto check = [&](int mx) -> bool{
            // 递归DFS：检查从(i,j)能否到达终点
            // 定义递归DFS为普通函数
            function<bool(int, int)> dfs = [&](int i, int j) -> bool {
                // 到达终点，返回true
                if(i == n - 1 && j == n - 1) {
                    return true;
                }

                vis[i][j] = mx; // 标记当前单元格在本次检查中已访问

                // 遍历四向邻居
                for(auto& dir : dirs) {
                    int x = i + dir[0], y = j + dir[1];
                    // 检查条件：
                    // 1. 邻居在网格范围内
                    // 2. 邻居高度 <= 当前水位mx（可淹没）
                    // 3. 邻居在本次检查中未访问过（vis[x][y] != mx）
                    // 4. 递归检查邻居能否到达终点
                    if(0 <= x && x < n && 0 <= y && y < n 
                       && grid[x][y] <= mx && vis[x][y] != mx 
                       && dfs(x, y)) {
                        return true;
                    }
                }
                return false; // 此路径无法到达终点
            };

            // 从起点开始检查，需确保起点高度 <= mx（否则直接不可行）
            return grid[0][0] <= mx && dfs(0, 0);
        };

        // 二分查找范围优化：
        // 最小可能时间至少是起点和终点的最大高度（需同时淹没两者）
        int left = max(grid[0][0], grid[n - 1][n - 1]) - 1;
        // 最大可能时间为n²-1（网格值最大可能为n×n-1，如按0~n²-1排列）
        int right = n * n - 1;

        // 二分查找：寻找最小的可行水位
        while(left + 1 < right) {
            int mid = left + (right - left) / 2;
            // 若mid可行，尝试更小值（收缩右边界）；否则尝试更大值（收缩左边界）
            if(check(mid)) {
                right = mid;
            } else {
                left = mid;
            }
        }

        return right; // 循环结束后，right为最小可行水位
    }
};